|
An XOR linked list is a data structure used in computer programming. It takes advantage of the bitwise XOR operation to decrease storage requirements for doubly linked lists. == Description == An ordinary doubly linked list stores addresses of the previous and next list items in each list node, requiring two address fields: ... A B C D E ... –> next –> next –> next –> <– prev <– prev <– prev <– An XOR linked list compresses the same information into ''one'' address field by storing the bitwise XOR (here denoted by ⊕) of the address for ''previous'' and the address for ''next'' in one field: ... A B C D E ... <–> A⊕C <-> B⊕D <-> C⊕E <-> More formally: link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), ... When you traverse the list from left to right: supposing you are at C, you can take the address of the previous item, B, and XOR it with the value in the link field (B⊕D). You will then have the address for D and you can continue traversing the list. The same pattern applies in the other direction. i.e. addr(D) = link(C) ⊕ addr(B) where link(C) = addr(B)⊕addr(D) so addr(D) = addr(B)⊕addr(D) ⊕ addr(B) addr(D) = addr(B)⊕addr(B) ⊕ addr(D) since X⊕X = 0 => addr(D) = 0 ⊕ addr(D) since X⊕0 = x => addr(D) = addr(D) The XOR operation cancels addr(B) appearing twice in the equation and all we are left with is the addr(D). To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one. If the addresses of the two consecutive items are reversed, you will end up traversing the list in the opposite direction. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「XOR linked list」の詳細全文を読む スポンサード リンク
|